package com.algorithm.homework.hard;

/**
 * 42. 接雨水
 *
 * <p>给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * <p>上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。 示例:
 *
 * <p>输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2020/6/26 22:52<br>
 */
public class TrappingRainWater {
  public int trap(int[] height) {
    int l = 0;
    int r = height.length - 1;
    int maxL = 0;
    int maxR = 0;
    int res = 0;
    while (l <= r) {
      if (maxL < maxR) {
        if (height[l] < maxL) {
          res += maxL - height[l];
        } else {
          maxL = height[l];
        }
        l++;
      } else {
        if (height[r] < maxR) {
          res += maxR - height[r];
        } else {
          maxR = height[r];
        }
        r--;
      }
    }
    return res;
  }
}
